#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;

class Solution{
    public:
    //my ans--只能处理t中字符不重复的情况
    string ans1(string s, string t){
        int len_s = s.size(), len_t = t.size();
        unordered_set<char> ch_t;
        string ret = "";
        if(len_t > len_s){
            return ret;
        }
        for(int i = 0; i != len_t; i++){
            ch_t.insert(t[i]);
        }
        vector<int> index;
        vector<char> ch;
        for(int i = 0; i != len_s; i++){
            if(ch_t.count(s[i])){
                index.push_back(i);
                ch.push_back(s[i]);
            }
        }
        int sub_len = ch.size();
        unordered_set<char> temp;
        int p = 0;
        int index_l = 0, index_r;
        int len = len_s;
        int ch_num = 0;
        for(int i = 0; i != sub_len; i++){
            if(i != 0){
                temp.erase(ch[i-1]);
                index_l = i;
                ch_num--;
            }
            while(p < sub_len && !temp.count(ch[p])){
                temp.insert(ch[p]);
                index_r = p;
                p++;
                ch_num++;
            }
            if(ch_num == len_t){
                int temp_len = index[index_r] - index[index_l] + 1;
                if(len >= temp_len){
                    len = temp_len;
                    ret = s.substr(index[index_l], temp_len);
                }
            }
        }

        return ret;
    }

    //暴力枚举--out of time
    string ans2(string s, string t){
        int len_s = s.size(), len_t = t.size();
        unordered_multiset<char> ch_t;
        unordered_multiset<char> ch_temp;
        if(len_t > len_s){
            return "";
        }
        for(int i = 0; i != len_t; i++){
            ch_t.insert(t[i]);
        }
        for(int sub_len = len_t; sub_len <= len_s; sub_len++){
            for(int i = 0; i != len_s - sub_len + 1 ; i++){
                string temp = s.substr(i, sub_len);
                int counts = 0;
                for(int j = 0; j != sub_len; j++){
                    ch_temp.insert(temp[j]);
                }
                for(int j = 0; j != len_t; j++){
                    if(ch_t.count(t[j]) <= ch_temp.count(t[j])){
                        counts++;
                    }else{
                        break;
                    }
                }
                ch_temp.clear();
                if(counts == len_t){
                    return temp;
                }
            }
        }
        return "";
    }

    //双边界--???
    string ans3(string s, string t){
        int len_s = s.size(), len_t = t.size();
        
    }
};

void test1(){
    Solution s;
    string str = "ADOBECODEBANC";
    string t = "ABC";
    // string ret = s.ans1(str, t);
    // string ret = s.ans2(str, t);
    string ret = s.ans3(str, t);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string str = "a";
    string t = "a";
    // string ret = s.ans1(str, t);
    // string ret = s.ans2(str, t);
    string ret = s.ans3(str, t);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string str = "jwsdrkqzrthzysvqqazpfnulprulwmwhiqlbcdduxktxepnurpmxegktzegxscfbusexvhruumrydhvvyjucpeyrkeodjvgdnkalutfoizoliliguckmikdtpryanedcqgpkzxahwrvgcdoxiylqjolahjawpfbilqunnvwlmtrqxfphgaxroltyuvumavuomodblbnzvequmfbuganwliwidrudoqtcgyeuattxxlrlruhzuwxieuqhnmndciikhoehhaeglxuerbfnafvebnmozbtdjdo";
    string t = "qruzywfhkcbovewle";
    // string ret = s.ans1(str, t);
    // string ret = s.ans2(str, t);
    string ret = s.ans3(str, t);
    cout << ret << endl;
}

void test4(){
    Solution s;
    string str = "aa";
    string t = "aa";
    // string ret = s.ans1(str, t);
    // string ret = s.ans2(str, t);
    string ret = s.ans3(str, t);
    cout << ret << endl;
}

void test5(){
    Solution s;
    string str = "aaaaaaaaaaaabbbbbcdd";
    string t = "abcdd";
    // string ret = s.ans1(str, t);
    // string ret = s.ans2(str, t);
    string ret = s.ans3(str, t);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();
    test4();
    test5();

    return 0;
}